UVa/11656 - Message in the Enemy Territory/11656.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXC = 1035;
  28
  29 bool blocked[MAXC][MAXC];
  30
  31 vector< int > YgivenX[MAXC], XgivenY[MAXC];
  32
  33 inline bool inside(int x, int y) {
  34     return (0 <= x and x < MAXC and 0 <= y and y < MAXC);
  35 }
  36
  37
  38 void markCorner(int x, int y, int m) {
  39     for (int xx = x - m; xx <= x + m; ++xx) {
  40         for (int yy = y - m; yy <= y + m; ++yy) {
  41             if (!inside(xx, yy)) continue;
  42             if ( (xx - x) * (xx - x) + (yy - y) * (yy - y) <= m * m ) { // very close to the border, or ON the border
  43                 blocked[xx][yy] = true;
  44             }
  45         }
  46     }
  47 }
  48
  49 void markHorizontalLine(int x0,  int x1,  int y,    int m) {
  50     for (int xx = x0; xx <= x1; ++xx) {
  51         for (int yy = y - m; yy <= y + m; ++yy) {
  52             if (!inside(xx, yy)) continue;
  53             blocked[xx][yy] = true;
  54         }
  55     }
  56 }
  57
  58 void markVerticalLine(int y0, int y1,    int x,     int m) {
  59     for (int yy = y0; yy <= y1; ++yy) {
  60         for (int xx = x - m; xx <= x + m; ++xx) {
  61             if (!inside(xx, yy)) continue;
  62             blocked[xx][yy] = true;
  63         }
  64     }
  65 }
  66
  67
  68 bool canReach(int sx, int sy,   int fx,  int fy) {
  69     assert(inside(sx, sy) and (fx, fy));
  70     assert(!blocked[sx][sy]);
  71     assert(!blocked[fx][fy]);
  72     queue< pair< int, int > > q;
  73     blocked[sx][sy] = true;
  74     q.push( make_pair(sx, sy) );
  75     while (q.size()) {
  76         int cx = q.front().first, cy = q.front().second;
  77         if (cx == fx and cy == fy) return true;
  78         q.pop();
  79         assert(blocked[cx][cy]);
  80         for (int dx = -1; dx <= +1; dx++) {
  81             for (int dy = -1; dy <= +1; dy++) {
  82                 int nx = cx + dx;
  83                 int ny = cy + dy;
  84                 if (!inside(nx, ny)) continue;
  85                 if (blocked[nx][ny]) continue;
  86                 blocked[nx][ny] = true;
  87                 q.push(  make_pair(nx, ny)  );
  88             }
  89         }
  90     }
  91     return false;
  92 }
  93
  94
  95 int main(){
  96     int n, m;
  97     while (cin >> n >> m) {
  98         if (n == 0 and m == 0) break;
  99
 100         assert(n % 2 == 0);
 101
 102         For(i, 0, MAXC) YgivenX[i].clear(), XgivenY[i].clear();
 103         memset(blocked, 0, sizeof blocked);
 104
 105         For(i, 0, n) {
 106             int x, y; cin >> x >> y;
 107             XgivenY[y].push_back( x );
 108             YgivenX[x].push_back( y );
 109         }
 110         int x1, y1, x2, y2;
 111         cin >> x1 >> y1 >> x2 >> y2;
 112
 113         For(x, 0, MAXC) {
 114             sort(YgivenX[x].begin(), YgivenX[x].end());
 115             assert(YgivenX[x].size() % 2 == 0);
 116             for (int k = 0; k < YgivenX[x].size(); k += 2) {
 117                 int y = YgivenX[x][k];
 118                 int nextY = YgivenX[x][k+1];
 119
 120                 markVerticalLine(y, nextY,   x,   m);
 121                 markCorner(x, y, m);
 122                 markCorner(x, nextY, m);
 123             }
 124         }
 125
 126         For(y, 0, MAXC) {
 127             sort(XgivenY[y].begin(), XgivenY[y].end());
 128             assert(XgivenY[y].size() % 2 == 0);
 129             for (int k = 0; k < XgivenY[y].size(); k += 2) {
 130                 int x = XgivenY[y][k];
 131                 int nextX = XgivenY[y][k+1];
 132
 133                 markHorizontalLine(x, nextX,  y,  m);
 134                 markCorner(x, y, m);
 135                 markCorner(nextX, y, m);
 136             }
 137         }
 138         if (canReach(x1, y1,  x2, y2)) {
 139             puts("Yes");
 140         } else {
 141             puts("No");
 142         }
 143     }
 144     return 0;
 145 }